package com.rn.gypsophila.dsalg.arrary;

import java.util.Arrays;

/**
 * 题目：给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
 * 链接：<a href="https://leetcode.cn/leetbook/read/array-and-string/cuxq3/">...</a>
 * 思路：
 * 1.先得出遍历的次数，即对角线条数为 m+n-1，故 i < m+n-1
 * 2.分治：根据奇偶对角线遍历，对角线特性 x+y=i
 * 3.偶对角线：起始点的 x 坐标为 min(i,n-1)，结束点的 x 坐标为 max(0,i-(m+1))
 * 4.奇对角线：起始点的 x 坐标为 max(0,i-m+1)，结束点的 x 坐标为 min(i,n-1)
 *
 * @author 然诺
 * @since 2023/2/27
 */
public class FindDiagonalOrder {

    public static int[] findDiagonalOrder(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[] ret = new int[m * n];
        int idx = 0, loop = m + n - 1;
        for (int i = 0; i < loop; i++) {
            if (i % 2 == 0) {
                for (int x = Math.min(i, n - 1); x >= Math.max(0, i - m + 1); x--) {
                    ret[idx++] = mat[x][i - x];
                }
            } else {
                for (int x = Math.max(0, i - m + 1); x <= Math.min(i, n - 1); x++) {
                    ret[idx++] = mat[x][i - x];
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[][] mat = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        System.out.println(Arrays.toString(findDiagonalOrder(mat)));
    }
}
